#define _FILE_OFFSET_BITS 64
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct Node {
    size_t id;
    size_t size;
    size_t isFree;
    void* addr; 
    struct Node *next;
} Node;

struct Node *head = NULL;
void *buffer; //for malloc

void push(Node **head, int id, int size, void* addr) {
    Node *tmp = (Node*) malloc(sizeof(Node));
    tmp->id = id;
    tmp->size = size;
    tmp->addr = addr;
    tmp->isFree = 1;
    tmp->next = (*head);
    (*head) = tmp;
}

Node* getNth(Node* head, int n) {
    int counter = 1;
    while (counter < n && head) {
        head = head->next;
        counter++;
    }
    return head;
}

Node* getById(Node* head, int id) {
	Node *tmp = (Node*) malloc(sizeof(Node));
    tmp = head;
    
    while (tmp->id != id && tmp != NULL) {
        tmp = tmp->next;
    }
    return tmp;
}

Node* getLast(Node *head) {
    if (head == NULL) {
        return NULL;
    }
    while (head->next) {
        head = head->next;
    }
    return head;
}

void deleteList(Node **head) {
    Node* prev = NULL;
    while ((*head)->next) {
        prev = (*head);
        (*head) = (*head)->next;
        free(prev);
    }
    free(*head);
}

void printLinkedList(const Node *head) {
    while (head) {
        printf("id = %zd, size = %zd\n", head->id, head->size);
        head = head->next;
    }
    printf("\n");
}

int power(int x, int y) {
	int j = 0, result = 1;
	
	for(j = 0; j < y; j++)
		result *= x;
		
	return result;
}

int ma_init(size_t mem) {
	
	buffer = (void*)malloc(mem);
	
	if(buffer == NULL) 
		return 0;
	else {
		//filling struct Node
		int sum = mem, i = 1, temp = 0;

		while(sum > 0) {
			temp = power(2, i);	
					
			if(sum < temp)
				temp = sum;	
				
			push(&head, i, temp, buffer+temp-2);			
			i++;
			sum -= temp;
		}		
		return 1;
	}
}

void ma_deinit() {
	deleteList(&head);
	free(buffer);
}

size_t ma_alloc(size_t sz) {
	
	Node *tmp = (Node*) malloc(sizeof(Node));
    tmp = head;
    
    size_t delta = sz, minDelta = tmp->size, id = 0;
	
    while (tmp != NULL) {
		if(tmp->size >= sz && tmp->isFree == 1) {
			
			if(tmp->size == sz) 
				return tmp->id;

			delta = tmp->size - sz;
						
			if(delta >=0 && delta < minDelta) {
				minDelta = delta;
				id = tmp->id;
			}
		}		
        tmp = tmp->next;
	}
			
	return id;
}

int ma_free(size_t id) {
	if(id <= 0 || id > (getLast(head)->id))
		return 0;
		
	Node *nd = getById(head, id);
		
	nd->isFree = 1;	
	return 1;
}

void* ma_get(size_t id) {
	Node *nd = getById(head, id);
	return nd->addr;
}
/*
int main() {
	
	//инициализация списка
	ma_init(60);
	//printf("%d\n", ma_init(60));	
	
	//вывод списка после инициализации - проверка
	printLinkedList(head);
	
	//вывод второго элемента
	Node *nd = getNth(head, 2);
    int resId, resSize;
    resId = nd->id;
    resSize = nd->size;
    printf("\n%d %d\n", resId, resSize);
	
	//вывод элемента по id 
	Node *nd2 = getById(head, 2);
    int res1, res2;
    res1 = nd2->id;
    res2 = nd2->size;
    printf("\n%d %d\n", res1, res2);
	
	//printf("\n%zd\n", head->id);
	
	//поиск id блока с подходящим размером
	printf("\nBlock's id for data = %zd\n", ma_alloc(17));
	//printf("%zd\n", head->id);
	
	//printf("\n%zd\n", head->id);
	
	printf("\nma_free(1) = %d\n", ma_free(1));
	printf("\nma_free(100) = %d\n", ma_free(100));
	
	
	//удаление списка и буфера
	ma_deinit();
	//printLinkedList(head);
	
	return 0;
}
*/
